#include <iostream>
using namespace std;

/// @brief 二叉树排序节点
typedef struct BSTNode
{
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

/// @brief 在二叉排序树中查找值为key的节点
/// @param T
/// @param key
/// @return
BSTNode *BST_Search(BSTree T, int key)
{
    while (T != NULL && key != T->key)
    { // 若树空或者等于根节点值时，则结束循环
        if (key < T->key)
        {
            T = T->lchild; // 小于，则在左子树上查找
        }
        else
        {
            T = T->rchild; // 大于，则在右子树上查找
        }
    }
    return T;
}

/// @brief 在二叉排序树中查找值为key的节点（递归实现）
/// @param T
/// @param key
/// @return
BSTNode *BSTSearch(BSTree T, int key)
{
    if (T == NULL)
    {
        return NULL; // 查找失败
    }
    if (key == T->key)
    {
        return T; // 查找失败
    }
    else if (key < T->key)
    {
        return BSTSearch(T->lchild, key); // 在左子树中找
    }
    else
    {
        return BSTSearch(T->rchild, key); // 在右子树中找
    }
}

/// @brief 在二叉排序树插入关键字为k的新节点（递归实现）
/// @param T
/// @param k
/// @return
int BST_Insert(BSTree &T, int k)
{
    if (T == NULL)
    { // 若树为空，则插入的节点为根节点
        T = (BSTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1; // 返回1，插入成功
    }
    else if (k == T->key)
    { // 树中存在相同的关键字的节点，插入失败
        return 0;
    }
    else if (k < T->key)
    {
        return BST_Insert(T->lchild, k); // 插入到T的左子树
    }
    else
    {
        return BST_Insert(T->rchild, k); // 插入到T的右子树
    }
}

/// @brief 按照str[]中的关键字序列建立二叉排序树
/// @param T
/// @param str
/// @param n
void Create_BST(BSTree &T, int str[], int n)
{
    T = NULL; // 初始时T为空树
    int i = 0;
    while (i < n)
    { // 依次将每个关键字插入到二叉排序树中
        BST_Insert(T, str[i]);
        ++i;
    }
}
